package src.数据结构.链表.双向链表;

import src.数据结构.链表.Node;

public class TowWayLinkList<T> {
    private Node<T> head; // 头节点
    private Node<T> tail; // 尾节点
    private int N; // 链表长度

    public TowWayLinkList() {
        // 初始化链表
        this.head = new Node(null, null, null);
        this.tail = null;
        this.N = 0;
    }


    // 判断表是否为空
    public boolean isEmpty() {
        return this.N == 0;
    }

    // 获取表大小
    public void size() {
        System.out.println("元素个数：" + this.N);
    }

    // 返回指定索引的值
    public T get(int index) {
        if (isEmpty()) {
            return null;
        }
        Node n = head.next;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return (T) n.item;
    }

    // 获取第一个节点
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return (T) this.head.next.item;
    }

    // 获取最后一个节点
    public T getEnd() {
        if (isEmpty()) {
            return null;
        }
        return (T) this.tail.item;
    }

    // 插入数据
    public void add(T t) {
        // 如果表为空
        if (isEmpty()) {
            // 创建新节点
            Node newNode = new Node(this.head, t, null);
            // 新节点成为尾节点
            this.tail = newNode;
            // 头节点指向尾节点
            head.next = this.tail;
        }
        // 如果表不为空
        else {
            Node oldLast = this.tail;

            // 让当前尾节点指向新节点
            Node newNode = new Node(this.tail, t, null);
            // 当前尾节点指向新节点
            oldLast.next = newNode;
            // 新节点成为尾节点
            this.tail = newNode;
        }
        this.N++;
    }

    public void insert(int i, T t) {
        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int j = 0; j < i; j++) {
            pre = pre.next;
        }
        // 找到i位置的节点
        Node curr = pre.next;
        // 创建新节点
        Node<T> newNode = new Node<>(pre, t, curr);
        // 让i位置前一个节点指向新节点
        pre.next = newNode;
        // 让i位置的上一个节点指向新节点
        curr.pre = newNode;
        this.N++;
    }

    // 删除数据
    public T pop(int index) {
        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int j = 0; j < index; j++) {
            pre = pre.next;
        }
        // 找到i位置节点
        Node<T> i_item = pre.next;
        //找到i位置下一个节点
        Node<T> i_next = i_item.next;
        // 让i位置前应该节点指向i位置的下一个节点
        pre.next = i_next;
        i_next.pre = pre;
        this.N--;
        return i_item.item;
    }

    public T pop() {
        Node<T> end = this.tail;
        this.tail = this.tail.pre;
        this.tail.next = null;
        this.N--;
        return end.item;
    }

    // 清空数据
    public void clear() {
        this.head.next = null;
        this.head.pre = null;
        this.head.item = null;
        this.tail = null;
        this.N = 0;
    }

    // 查询元素的索引
    public int indexOf(T t) {
        Node n = head;
        for (int i = 0; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }

    public void show() {
        Node<T> n = head;
        while (n.next != null) {
            n = n.next;
            System.out.print(n.item + " ");
        }
        System.out.println();
    }

    // 快慢指针获取链表中间值
    public void getMid() {
        Node n1 = this.head; // 快指针
        Node n2 = this.head; // 慢指针
        while (n1 != null && n1.next != null) {
            n1 = n1.next.next;
            n2 = n2.next;
        }
        System.out.println("链表中间值为：" + n2.item);
    }

    // 使用快慢指针判断链表是否有环
    public boolean isRing(){
        if (this.head == null) {
            return false;
        }
        /* 头节点不存储数据所以需要指定到头节点的下一个节点为起点 */
        Node n1 = this.head.next; // 快指针
        Node n2 = this.head.next; // 慢指针
        while (n1 != null && n1.next != null) {
            n1 = n1.next.next;
            n2 = n2.next;
            if(n1.equals(n2)){
                return true;
            }
        }
        return false;
    }

    // 构建环形链表 尾节点指向头节点即可
    public void ring(){
        if (this.head == null) {
            System.out.println("链表为空");
            return;
        }
        Node n = this.head;
        while (n.next!=null){
            n = n.next;
        }
        n.next = this.head;
    }


}
